/**
 * 堆排序
 * @param {*} arr 
 * @returns nlogn
 */
function heapSort(arr){
    var heapSize=arr.length,temp;
    for(var i=Math.floor(heapSize/2)-1;i>=0;i--){
        heapify(arr,i,heapSize);
    }
    for(let j=heapSize-1;j>=1;j--){
        temp=arr[0];
        arr[0]=arr[j];
        arr[j]=temp;
        heapify(arr,0,--heapSize);
    }
    return arr;
}
/**
 * 构建堆 维护堆
 * @param {*} arr 
 * @param {*} x 
 * @param {*} len 
 */
function heapify(arr,x,len){
    let l=2*x+1,r=2*x+2,largest=x,temp;
    if(l<len&&arr[l]>arr[largest]){
        largest=l;
    }
    if(r<len&&arr[r]>arr[largest]){
        largest=r 
    }
    if(largest!=x){
        temp=arr[x];
        arr[x]=arr[largest];
        arr[largest]=temp;
        heapify(arr,largest,len);
    }
}

var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));